package LeetCodeHot100;

/**
 * leetCode 148 排序链表
 *
 * 链表排序：可以采用归并排序
 */
public class LeetCode148 {

    public ListNode sortList(ListNode head) {
        return sortList(head,null);
    }

    private ListNode  sortList(ListNode head,ListNode tail){
        if(head == null){
            return head;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }
        // 使用快慢指针获取链表的中间节点
        ListNode slow = head,fast = head;
        while (fast!=tail){
            slow = slow.next;
            fast = fast.next;
            // 加这一手就是为了防止溢出
            if(fast!=tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    /**
     * 合并排序函数
     */
    private ListNode merge(ListNode head1, ListNode head2){
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead,temp1 = head1,temp2 = head2;
        while (temp1!=null && temp2!=null){
            if(temp1.val <= temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            // 如果说返回结果总是返回单个元素，没有集合的排序，一般就是循环出了问题，没有下一步了，这一点需要记好
            temp = temp.next;
        }
        if(temp1 != null){
            temp.next = temp1;
        }else if(temp2 != null){
            temp.next = temp2;
        }
        return dummyHead.next;
    }

     public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
